/*COPYRIGHT NOTICE: This software is provided by United States Postal Service 
(USPS). It can be used only for ID-tag applications which make use of ID-tags 
in conformity with UPU standard S18c. The software may be freely distributed 
and/or modified.  A condition of such distribution is that this copyright 
notice is always included in the comments heading the software. This software 
is licensed as is without any other warranty of any kind. USPS expressly 
disclaims all warranties or conditions including, but not limited to, implied 
warranties or conditions of merchantability and fitness for particular purpose 
and those arising by statute or otherwise in law or from course of dealing or 
usage of trade. In no event shall USPS be liable for any direct, indirect, 
special, incidental, consequential or other damages arising out of this 
software even if USPS has been advised of the possibility of such damages in 
advance.
*/
/*
*   This module contains the function ncorrect_to_info which validates 
*   and corrects an S18c format ID-tag bar code.
*
*   Principal function in this module is:
*   ncorrect_to_info(infon *info, int *bars);
*		Correct errors in bar code
*		Convert corrected bar code into info, being:
*			cbit:		value of the Cbit
*			machine:	machine number in range 0001-3999
*			day:		day of month in range 01-31
*			time:		time of day in half hour increments, range 00-47
*			sequence:	item sequence number, range 00001-24999
*
*        Returns number of errors corrected, or -1 if not correctable.
*
*	Subsidiary functions are:
*		bars_to_bits:	converts bar code to bit string and ecc string
*		make_ecc:		used by correct to calculate ecc and parity bits
*		count_bits:		subfunction of correct used in parity checking
*		correct:		corrects bit string derived from bar code
*		bits_to_group:	subfunction of bits_to_info
*		bits_to_info:	converts corrected bit string to data values
*
*/

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#include <io.h>
#include <fcntl.h>
#include <sys\stat.h>

/* National ID Tag Data */
typedef struct
    {
    unsigned cbit;		/* Cbit */
    unsigned machine;	/* machine id, range 0001-3999 */
    unsigned day;		/* day of month, range 01-31 */
    unsigned time;		/* 00-47, half hour increments */
    unsigned sequence;	/* mailpiece sequence number, 00001-24999 */
    } infon;

/* function definitions */
int  ncorrect_to_info(infon *info, int *bars);

#define DATA_LENGTH 47   /* actual length of data */
#define CRCLEN 12        /* length of CRC */
#define GENERATOR 0x1539 /* generator polynomial x12+x10+x8+x5+x4+x3+1 */
#define GENHI     0x1000 /* the x12 term where the data goes */

/*************  DATA VARIABLES ****************/

static int bits[47];           /* data bits only */
static int eccbits;            /* ecc bits extracted from *bars */
static int parbit;             /* the parity bit */
static int this_ecc;           /* ecc bits calculated from bits[] */

/* Values[] is the inverse of codes[] (in the module for generating S18c
 * bar codes), for looking up the coded value of a group. -1 indicates 
 * invalid patterns. Note that this table is based on inverted-bit group
 * values used in the data section of the bar code.
 */
/*                  bit patterns                               values    */
static int values[]= { 0, 1, 2, 3, 4, 5, 6,-1,                /* 0x00-07 */
                       8, 9,-1, 7,-1,-1,-1,-1};               /* 0x08-0F */

/*************  FUNCTION DECLARATIONS ****************/

static void bars_to_bits(int *bars);
static void make_ecc(void);
static int count_bits(int e);
static int  correct(int *bars);
static int  bits_to_group(int start, int length);
static int  bits_to_info(infon *info);

/*************  THE FUNCTIONS ***************/

static void bars_to_bits(int *bars)
    /* re-order bars[] to bits[] */
    /* used by ncorrect_to_info */
{
int i;

    for (i=0; i<3; i++)
        bits[i] = bars[i+1];     /* CM3 */  /* offset = start bit */
    for (i=3; i<7; i++)
        bits[i] = bars[i+2];     /*  M2 */  /* offset = start + E11 */
    for (i=7; i<11; i++)
        bits[i] = bars[i+3];     /*  M1 */
    for (i=11; i<15; i++)
        bits[i] = bars[i+4];     /*  M0 */
    for (i=15; i<18; i++)
        bits[i] = bars[i+5];     /*  D1 */
    for (i=18; i<22; i++)
        bits[i] = bars[i+6];     /*  D0 */
    for (i=22; i<25; i++)
        bits[i] = bars[i+7];     /*  T1 */
    for (i=25; i<29; i++)
        bits[i] = bars[i+8];     /*  T0 */
    for (i=29; i<31; i++)
        bits[i] = bars[i+9];     /*  S4 */
    for (i=31; i<35; i++)
        bits[i] = bars[i+10];    /*  S3 */
    for (i=35; i<39; i++)
        bits[i] = bars[i+11];    /*  S2 */
    for (i=39; i<43; i++)
        bits[i] = bars[i+12];    /*  S1 */
    for (i=43; i<47; i++)
        bits[i] = bars[i+13];    /*  S0 */  /* offset = start + E11..E0 */
    eccbits  = bars[4] << 11;    /* E11 */
    eccbits |= bars[9] << 10;    /* E10 */
    eccbits |= bars[14] << 9;    /* E9 */
    eccbits |= bars[19] << 8;    /* E8  */
    eccbits |= bars[23] << 7;    /* E7  */
    eccbits |= bars[28] << 6;    /* E6  */
    eccbits |= bars[32] << 5;    /* E5  */
    eccbits |= bars[37] << 4;    /* E4  */
    eccbits |= bars[40] << 3;    /* E3  */
    eccbits |= bars[45] << 2;    /* E2  */
    eccbits |= bars[50] << 1;    /* E1  */
    eccbits |= bars[55];         /* E0  */
    parbit   = bars[60];         /* Ep  */
}

static void make_ecc(void)
    /* Generate correct this_ecc and parbit matching data in bits[0..46] */
    /* Used by both ninfo_to_bars and correct */
{
int i,j;

    this_ecc = 0;
    parbit = 0;
    for (i=0; i<47; i++)
        {
	    this_ecc <<= 1;			/* left-shift one bit */
	    if (bits[i])
            {
            parbit ^= 1;		/* XOR the parity bit */
	        this_ecc ^= GENHI;	/* XOR the data bit */
            }
	    if (this_ecc & GENHI)		/* replace 12-bit carry+data with generator */
	        this_ecc ^= GENERATOR;	/* binary 010100111001, & turn off GENHI */
	    }

    j = this_ecc;
    for (i=0; i<12; i++)
        {
        parbit ^= (j&1);
        j >>= 1;
        }
}

static int count_bits(int e)
    /* Count and return number of bits in parameter */
    /* Used by correct */
{
int i,j;

    for (i=0,j=0; i<CRCLEN; i++)
        {
        if (e & 0x0001)
            j++;
        e >>= 1;
        }
    return(j);
}

static int correct(int *bars)
    /* This function returns the number of errors corrected as a positive
     * number if it thinks it found the correct data (0 if no errors),
     * else returns a negative error code.
     *
     * Used by ncorrect_to_info
     *
     * Input data is in global variables:
     * bits[] contains the info to be corrected.
     * eccbits contains the ecc extracted from input bars[].
     * bars[60] contains the input parity bit.
     *
     * Note this function ignores start/stop bits at bars[0,61]; uncertainty
     * as to position should be considered an additional error.
     *
     * Also, although sometimes technically possible, three or more errors
     * are considered too unreliable and are rejected as uncorrectable, so
     * the maximum value returned by this function is 2.
     */
{
int i,j;
unsigned u;
unsigned syndrome;
unsigned g; /* generate GENnn table here */
unsigned d; /* difference between syndrome and g */

        make_ecc();   /* calculate this_ecc and parbit from bits[] */
        syndrome = eccbits ^ this_ecc;       /* error syndrome */
        i = count_bits(syndrome);
        if (i==0)
            {
            /* No CRC corrections */
            if (parbit == bars[60])
                return(0);                   /* no errors detected */
            else
                return(1);                   /* parity bit error */
            }
        if (i==1)
            {
            /* 1-bit CRC error */
            if (parbit == bars[60])
                return(1);                   /* one CRC bit error */
            else
                return(2);                   /* one CRC and parity bit */
            }
        if (i==2)
            {
            /* 2-bit CRC error */
            if (parbit == bars[60])
                return(2);                   /* two CRC bit errors */
            else
                return(-1);                  /* uncorrectable error */
            }

        /* Now we have to look for data-bit errors; this will
         * take a while since we insist on doing it without any
         * table lookup, just to prove it's possible!
         */
        g = GENHI;
        g >>= 1;   /* genhi after first left shift */
        for (i=0; i<DATA_LENGTH; i++)       /* for each GENxx table entry g */
            {
            g <<= 1;                        /* calculate g = this bit's ECC */
            if (g & GENHI)
                g ^= GENERATOR;

            /* syndrome matches this entry? */
            d = g ^ syndrome;  /* d = subtract this bit's ECC from syndrome */
            j = count_bits(d);
            if (j==0)
                {
                /* 1-bit data error found */
                bits[DATA_LENGTH-i-1] ^= 1;  /* correct the data error */
                make_ecc();                  /* make new parbit */
                if (parbit == bars[60])
                    return(1);               /* one data bit corrected */
                else
                    return(2);               /* one data and parity bit */
                }
            else if (j==1)
                {
                /* 1 data and 1 ECC error */
                bits[DATA_LENGTH-i-1] ^= 1;  /* correct the data error */
                make_ecc();                  /* make new parbit */
                if (parbit == bars[60])
                    return(2);               /* one data and one ecc bit */
                else
                    return(-2);              /* uncorrectable error */
                }
            else
                {
                /* Look for 2-data-bit error;
                 * found if syndrome_difference d matches GENnn entry.
                 * We will have to generate the whole table again to check.
                 */
                u = g;             /* can't be a bit we already checked */
                for (j=i+1; j<DATA_LENGTH; j++)
                    {
                    u <<= 1;                 /* calculate u = 2nd bit's ECC */
                    if (u & GENHI)
                        u ^= GENERATOR;
                    if (u == d)            /* if new ECC matches difference */
                        {
                        /* found 2-data-bit error */
                        bits[DATA_LENGTH-i-1] ^= 1;  /* correct data errors */
                        bits[DATA_LENGTH-j-1] ^= 1;
                        make_ecc();                  /* make new parbit */
                        if (parbit == bars[60])
                            return(2);               /* two data bits corrected */
                        else
                            return(-3);              /* uncorrectable error */
                        }
                    }
                }
            }

        return(-4);            /* couldn't correct the error */
}

static int bits_to_group(int start, int length)
    /* returns data value matching a string of bits[] */
    /* used by bits_to_inf0 */
{
int i;

    for (i=0; length; length--)
        {
        i <<= 1;
        i += bits[start++]^0x01;
        }
    return(values[i]);
}

static int bits_to_info(infon *info)
    /* Convert bits[] to info */
    /* Check info values, return error code if out-of-range */
    /* Used by ncorrect_to_info */
{
int i;
unsigned u;

    /* Cbit; */
    if (bits[0])                     /* nobar */
        info->cbit = 0; 
    else
        info->cbit = 1; 

    /* machine;    machine id, range 0001-3999 */
    u = bits_to_group(1,2) * 1000;   /* M3 */
    i = bits_to_group(3,4);          /* M2 */
    if (i<0)
        return(1);
    else
        u += i * 100;
    i = bits_to_group(7,4);          /* M1 */
    if (i<0)
        return(2);
    else
        u += i * 10;
    i = bits_to_group(11,4);         /* M0 */
    if (i<0)
        return(3);
    else
        u += i;
    if (u>3999)
        return(4);
    info->machine = u;

    /* day;        day of month, range 01-31 */
    i = bits_to_group(15,3);         /* D1 */
    if (i<0)
        return(5);
    else
        u = i * 10;
    i = bits_to_group(18,4);         /* D0 */
    if (i<0)
        return(6);
    else
        u += i;
    if (u>31)
        return(7);
    info->day = u;

    /* time;       00-47, half hour increments */
    i = bits_to_group(22,3);         /* T1 */
    if (i<0)
        return(5);
    else
        u = i * 10;
    i = bits_to_group(25,4);         /* T0 */
    if (i<0)
        return(8);
    else
        u += i;
    if (u>47)
        return(9);
    info->time = u;

    /* sequence;   mailpiece sequence number, 00001-24999 */
    i = bits_to_group(29,2);         /* S4 */
    if (i>2)
        return(10);
    else
        u = i * 10000;
    i = bits_to_group(31,4);         /* S3 */
    if (i<0)
        return(11);
    else
        u += i * 1000;
    i = bits_to_group(35,4);         /* S2 */
    if (i<0)
        return(12);
    else
        u += i * 100;
    i = bits_to_group(39,4);         /* S1 */
    if (i<0)
        return(13);
    else
        u += i * 10;
    i = bits_to_group(43,4);         /* S0 */
    if (i<0)
        return(14);
    else
        u += i;
    if (u>24999)
        return(15);
    info->sequence = u;

    return(0);                                /* done, no errors detected */
}

int  ncorrect_to_info(infon *info, int *bars)
    /* Extract corrected info from bars */
    /* Return -1 (fail) or number of errors corrected */
{
int i;

    bars_to_bits(bars); /* extract data values including eccbits (not parbit) */

    i = correct(bars);            /* perform error correction on bits[] */
    if (i<0)
        return(-1);               /* uncorrectable error */
    else if (bits_to_info(info))  /* extract info from bits */
        return(-1);               /* out-of-range after correction */

    return(i);     /* success! - return # of errors corrected */
}
